"Toxic" được viết bởi Cathy Dennis, Henrik Jonback, Christian Karlsson và Pontus Winnberg từ đội sản xuất Bloodshy and Avant, ngoài ra họ cũng là đồng sản xuất.[1] Bài hát lúc đầu được viết cho nữ ca sĩ Kylie Minogue trong album phòng thu thứ chín của cô ấy, Body Language (2003), nhưng cô ấy không chấp nhận. Sau đó thì Minogue đã bình luận: "Tôi đã không hề tức giận (nuối tiếc) về việc bài hát đem lại thành công vang dội cho cô ấy (Spears). Việc đó y hệt như việc phóng sinh một con cá nhỏ vậy, chỉ cần cho đi là xong."[2] "Toxic" được thu âm lại ở phòng thu Murlyn Studios tại Stockholm (Thụy Điển) và tại Record Plant ở Los Angeles (Mỹ). Sau đó thì ca khúc cũng được phối âm lại bởi Niklas Flyckt tại phòng thu Khabang ở Stockholm.[1] Vào tháng 12 năm 2003, MTV News thông báo về việc sau khi xem xét "(I Got That) Boom Boom" và "Outrageous", Spears quyết định chọn "Toxic" làm đĩa đơn thứ hai của In The Zone thay vì hai bài hát trên.[3] Cô miêu tả rằng "nó là một bài hát thật sôi động và khác biệt, đó là lý do tại sao tôi lại thích nó."[4]